#leetcode题目300：最长递增子数列
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(n)
#方法：动态规划
#leetcode:https://leetcode.cn/problems/longest-increasing-subsequence/description/



#题目理解：
#以当前数字作为结尾时，最长递增序列长度
#  也就是以第几个数字作为结尾时候，其实是可以求出当前所能够有的最长的序列长度，然后依次类推，把每一个数作为结束的情况子序列长度，
# 然后找出里面最长的即可，变成了n个的问题，这里面可以用上一个数字作为结尾的结果，（这其实可以节省很多计算量，）这样下面的一个可以判断一下是否在此基础上加一个。

#时间复杂度：n种情况(指的是数组的长度为n)每种都要和前面的进行比较。所以是n^2
from typing import List



class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        最长递增子序列
        给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
        子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
        例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
        """
        # 基础情况：空数组
        if not nums:
            return 0
        
        n = len(nums)
        # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        dp = [0] * n
        dp[0] = 1  # 第一个元素本身构成长度为1的递增子序列
        
        max_length = 1  # 记录全局最大长度
        
        # 遍历数组，计算以每个元素结尾的最长递增子序列长度
        for i in range(1, n):
            dp[i] = 1  # 每个元素本身至少构成长度为1的递增子序列
            
            # 检查所有在 i 之前的元素
            for j in range(i):
                # 如果 nums[i] > nums[j]，说明 nums[i] 可以接在 nums[j] 后面
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)#状态转移方程
            
            # 更新全局最大长度
            max_length = max(max_length, dp[i])
        
        return max_length




#测试数据
nums = [10,9,2,5,3,7,101,18]
#预期输出：4,最长递增子数列是[2,3,7,101]
solution = Solution()
print(solution.lengthOfLIS(nums))

nums = [0,1,0,3,2,3]
#预期输出：4,最长递增子数列是[0,1,2,3]
solution = Solution()
print(solution.lengthOfLIS(nums))

nums = [7,7,7,7,7,7,7]
#预期输出：1,最长递增子数列是[7]
solution = Solution()
print(solution.lengthOfLIS(nums))


